# for AStar feather
# class Node()
# class Astar()
import random
from setup import *

class Node():
    def __init__(self,point):
        self.x=point[0]
        self.y=point[1]
        self.g=0
        self.h=0
        self.f=0
        self.father=None
    
    def __eq__(self,other):
        return self.x==other.x and self.y==other.y

class Astar():
    def __init__(self,begin,end):
        self.openlist=[]
        self.closelist=[]
        self.mhds=[(0,-1),(-1,0),(0,1),(1,0)]
        self.begin=Node(begin)
        self.end=Node(end)

    def search(self):
        if len(self.openlist)==0:
            self.openlist.append(self.begin)
        
        while len(self.openlist):
            sort_list=sorted(self.openlist,key=lambda node:node.f)
            minf_node=sort_list[0]

            if minf_node == self.end:
                self.end.father=minf_node.father
                return self.save_path()
            else:
                if minf_node not in self.closelist:
                    self.closelist.append(minf_node)
                    self.openlist.remove(minf_node)
                random.shuffle(self.mhds)
                for mhd in self.mhds:
                    temp_x=minf_node.x+mhd[0]
                    temp_y=minf_node.y+mhd[1]

                    if self.in_map((temp_x,temp_y)):
                        new_node=Node((temp_x,temp_y))

                        if new_node in self.openlist:
                            index=self.openlist.index(new_node)
                            if self.openlist[index].g>minf_node.g+1:
                                self.openlist[index].g=minf_node.g+1
                                self.openlist[index].father=minf_node
                        else:
                            if new_node not in self.closelist:
                                new_node.g=minf_node.g+1
                                new_node.h=self.get_h(new_node)
                                new_node.f=new_node.g+new_node.h
                                new_node.father=minf_node
                                self.openlist.insert(0,new_node)
                    else:
                        return None

    def save_path(self):
        my_path=[]
        cur_node=self.end

        while cur_node:
            my_path.append((cur_node.x,cur_node.y))
            cur_node=cur_node.father

        return my_path[::-1]

    def in_map(self,point):
        if 0<=point[0]<=GRID[0]-1 and 0<=point[1]<=GRID[1]-1:
            return True
        else:
            return False

    def get_h(self,node):
        return abs(self.end.x-node.x)+abs(self.end.y-node.y)                




